Network processors often are employed for transmitting data into and out of devices coupled to a network (e.g., switches, routers, etc.). One such network in which network processors are employed is an asynchronous transfer mode (ATM) network.
In an ATM network, data is transmitted using cells that include 48 bytes of information fields and 5 bytes of header fields. Routing occurs via virtual channel connections and virtual path connections, with virtual channel connections being addressed using a 16-bit virtual channel-identifier (VCI) and virtual path connections being addressed using a 12-bit virtual path identifier (VPI). The VCI and VPI for a data cell form part of the 5 bytes of header fields of the data cell.
A 16-bit VCI allows for 216=65,536 unique virtual channel connections, and a 12-bit VPI allow for 212=4096 unique virtual path connections. Accordingly, 4096×65,536=268,435,456 connections are supported within an ATM network and at least an 8 Gbyte memory is required to accommodate the switching/control information for all of these connections (e.g., assuming a 32 byte control block size is employed). Despite such a large number of available connections, in practice, typically only tens, hundreds, or in some cases thousands, of connections are active within a network device/network processor coupled to an ATM network.
For each received cell, a network processor accesses one or more entries in a table (e.g., an off-chip memory) that contains a receive control block (RCB) for the cell. Each RCB may include, for example, switching/control information for received cells, and may be accessed via an RCB index.
An RCB index generally is based on the VPI and VCI fields of a received cell. Because each incoming port of a network processor may have an overlapping set of VPIs and VCIs, the port number of the port receiving a cell may be included in the RCB index. For example, to create an RCB index for a received cell, a mapping algorithm may be employed to select certain bits of the VPI, VCI and port number fields and to combine the bits to form the RCB index. The RCB index then may be shifted and added to a memory base offset to find the actual memory address of an RCB.
Straight mapping of VPI, VCI and/or port number field bits into an RCB index has disadvantages. For example, assume “X” VPI bits and “Y” VCI bits are employed for an RCB index. A corresponding memory that stores RCBs would be divided into 2x equal sections, and each section would be subdivided into 2Y equal subsections (e.g., representing X virtual paths each having Y virtual channels). Such an approach is inefficient in that all virtual paths are assumed to have the same number of virtual channels. In practice, however, the number of virtual channels per virtual path may vary, and the memory space for virtual paths having fewer than Y channels is wasted. That is, unused memory is allocated to RCBs that do not exist.
One conventional approach for creating an RCB index employs a 24 bit “strand” comprising 24 bits from the VPI and VCI fields of a received cell. Unused bits of the strand are zeroed, and the 24 bit strand is employed to address a table entry which contains a 16 bit memory address location of an RCB. Disadvantages of such an approach are that the logic required to create the 24 bit strand and the 224=16,777,216 (16 Mb) memory required for a 16 bit memory address space are duplicated for each port, and each 16 Mbyte memory is located off-chip (e.g., an external memory access is required for every cell received, consuming valuable memory bandwidth). Accordingly, improved methods and apparatus for indexing memory of a network processor would be desirable.